package graph.topsort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 图的拓扑排序（dfs/bfs 常见使用 bfs  )
 * 解决项目间依赖和组间依赖   分成两部分  组间依赖和组内依赖  用节点是否和依赖节点组号相同来判断   用bfs拓扑排序解决两个依赖是否成环即可
 * https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/chao-xiang-xi-shuang-ceng-tuo-bu-pai-xu-5cyuc/
 */
public class 项目管理_1203 {
    //                     n 个项目  m个小组   每个项目属于哪个小组  下标i之前必须有哪些项目先做完
    public int[] sortItems(int n,   int m,   int[] group,        List<List<Integer>> beforeItems) {
        // 未初始化
        List<List<Integer>> groupList = new ArrayList<>(); // 分组表
        // 未初始化
        List<Integer> groupIds = new ArrayList<>();  // 组号列表  0 ~ m+n

        for(int i = 0; i < m + n; i++)
            groupList.add(new ArrayList<>());
        for(int i = 0; i < m + n; i++)
            groupIds.add(i);

        int newGroupNo = m;
        for(int i = 0; i < n; i++) {
            if(group[i] == -1) group[i] = newGroupNo++;
            groupList.get(group[i]).add(i);              // 归类到组号表中
        }
        List<List<Integer>> groupGraph = new ArrayList<>(); // 组依赖  依赖于idx 完成的组列表
        List<List<Integer>> itemGraph = new ArrayList<>(); //  项目依赖

        // 初始化
        for(int i = 0; i < m + n; i++)
            groupGraph.add(new ArrayList<>());
        for(int i = 0; i < n; i++)
            itemGraph.add(new ArrayList<>());

        int[] groupIndegree = new int[m + n]; // 组的入度  因为 题中 “存在小组不负责任何项目，即没有任何项目属于这个小组” 传入的m组可能都是空组  入度需要 + m  https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/chao-xiang-xi-shuang-ceng-tuo-bu-pai-xu-5cyuc/
        int[] itemIndegree = new int[n];  // 项目的入度
        for (int i = 0; i < n; i++) {
            int groupId = group[i];   // 当前项目组号
            List<Integer> depends = beforeItems.get(i); // 当前项目 的依赖表
            for (int depend : depends) {
                int dependGroupId = group[depend];
                if(groupId == dependGroupId) {
                    // 相同的组  更新组内依赖
                    itemGraph.get(depend).add(i); // depend 指向 i
                    itemIndegree[i] ++;           // 增加 i的入度
                } else {
                    groupGraph.get(dependGroupId).add(groupId); // 组间 dependGroup 指向 本 group
                    groupIndegree[groupId] ++;                  // 增加group的入度
                }
            }
        }
        // 组间依赖是否成环 不成环输出组号列表
        List<Integer> sortedGroupId = topSort(groupIndegree, groupGraph, groupIds);
        if(sortedGroupId == null) return new int[0]; // new int[0] 表示空数组对象
        // 组内依赖是否成环  不成环把每个组成员依次写到返回里
        int[] res = new int[n];
        int index = 0;
        for (int groupId : sortedGroupId) {
            List<Integer> inners = groupList.get(groupId); // 通过组号拿组内元素
            List<Integer> sortedInners = topSort(itemIndegree, itemGraph, inners); // 组内排序
            if(sortedInners == null) return new int[0]; // new int[0] 表示空数组对象
            for(Integer item : sortedInners) {
                res[index++] = item;
            }
        }
        return res;
    }

    // 因为degree不一定对应nos中所有的no 可能有些不用  只需要排序 nos中的编号列表即可
    // 拓扑排序                         入度表                     后续节点表                 编号表
    private List<Integer> topSort(int[] degree, List<List<Integer>> graph, List<Integer> nos) {
        Queue<Integer> queue = new LinkedList<>(); // 编号依次入队
        List<Integer> answer = new ArrayList<>();
        for(int no : nos) {
            if(degree[no] == 0) queue.offer(no);
        }
        while (!queue.isEmpty()) {
            int no = queue.poll();
            answer.add(no);
            List<Integer> nexts = graph.get(no);
            for(int next : nexts) {
                if(--degree[next] == 0) queue.offer(next); // 入度为0 再次入列
            }
        }
        return answer.size() != nos.size() ? null : answer;  // 入度为0表示可以执行的项目 可以执行的个数与预期个数不等 表示不能排序  图中有环
    }
}
